package com.xyhuo.leetcode.december;

/**
 * 颜色分类
 * https://leetcode.cn/problems/sort-colors/
 *
 * @desc 快排实现
 * @time 2023/12/28
 */
public class SortColors {

//    public void sortColors(int[] nums) {
//        quickSort(nums, 0, nums.length - 1);
//    }

    private void quickSort(int[] nums, int i, int j) {
        if (i >= j) {
            return;
        }
        int val = nums[i];
        int left = i, right = j;
        while (left < right) {
            while (left < right && nums[right] > val) {
                right--;
            }
            if (left < right) {
                nums[left] = nums[right];
                left++;
            }
            while (left < right && nums[left] < val) {
                left++;
            }
            if (left < right) {
                nums[right] = nums[left];
                right--;
            }
        }
        nums[left] = val;
        quickSort(nums, i, left - 1);
        quickSort(nums, left + 1, j);
    }
}
